Python实现反转链表

之前在遇到这个题目的时候，一直没想明白递归是怎么做的。网络上介绍解法的文章很多，可是大多数不够详细。希望借着这篇文章分享我本人的思路，如有错误，欢迎指正。

题目来源于LeetCode 206，题目要求反转一个单链表。

先给上解题代码，再来详细分析是怎么做到翻转的。

ListNode类不多说，Python实现链表的常用形式。重点关注reverseList( )函数的实现过程。

1.首先函数进入开头的两个if语句，分别是用来判断当前节点和下一个节点是否为NULL，尤其是第二个,在后面递归过程中也会用到。

2.然后开始进入递归，注意传给 self.reverseList( ) 的参数为 head.next ,也就是说链表的会一直往后传递，直到找到最后一个节点（也就是head.val == 5的节点，后文简述为节点5）。此时，因为不满足第二个if语句，返回节点5。

我们可以在第二个if语句中加入一行print( head.val ) ，这样可以更容易看出返回的内容。

3.函数在第二步返回到递归的上一层，headNode 等于返回的节点5 , 也就是节点5作为反转的链表头，完成反转的第一步。

4. 当前节点head为节点4 , head.next指向节点5， head.next.next指向None。 head.next.next= head 让原来指向None的节点5，改为指向节点4，完成了5—>None到5—>4的反转；然后head.next = None , 作用在于截断节点4到节点5的指针，避免形成4—>5—>4的环。

5.同理，返回上一层，当前节点head为节点3，让节点4指向节点3，再截断节点3到节点4的指针。

6.如此重复，直到反转所有节点，headNode即为反转后的链表。